package algorithm.sort.array;


import algorithm.search.binary.redundency.FindLastSmallerThanTarget;

/**
 * @program: algorithm-data-structure
 * @description: bubbling sort method.
 * @author: Keyu Li
 * @create: 2021-08-30 09:51
 **/

public class SortInsertion implements SortingMethod {
    String name = "Insertion";

    @Override
    public String getName() {
        return name;
    }

    @Override
//    public void sort(int[] arr) {
//        int temp;
//        for (int i = 1; i < arr.length; i++) {
//            temp = arr[i];
//            int j = i - 1;
//            for (; j >= 0; j--) {
//                if (arr[j] > temp)
//                    arr[j + 1] = arr[j];
//                else
//                    break;
//            }
//            arr[j+1] = temp;
//        }
//    }

    public void sort(int[] arr){
        int temp;
        for (int i = 0; i < arr.length-1; i++) {
            temp = arr[i+1];
            int index = FindLastSmallerThanTarget.search(arr, temp, 0, i);
            for (int j = i+1; j >index+1 ; j--) {
                arr[j] = arr[j-1];
            }
            arr[index+1] = temp;
        }
    }
}
